class Solution {
public:
    //状态表示 dp[0][i][j] 走到这一格还剩下的生命值
    //        dp[1][j][1] 走到这一格所需要的初始生命值
    //状态转移方程 dp[i][j]=min(dp[i-1][j],dp[i][j])+dungeon[i][j]
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        vector<vector<vector<int>>>dp(2,vector<vector<int>>(dungeon));
        //0 0 0
        //1 1 -1
        //
        for(int i=0;i<dungeon.size();i++){
            for(int j=0;j<dungeon[i].size();j++){
                if(!i&&!j)continue;
                int up=i-1>=0?dp[0][i-1][j]:INT_MIN;
                int left=j-1>=0?dp[0][i][j-1]:INT_MIN;
                //从历史上最低血量跟高的位置来
                dp[0][i][j]=max(up,left);
                //选择从哪里来
                int from=up==left?max(dp[1][i-1][j],dp[1][i][j-1]):dp[0][i][j]==up?dp[1][i-1][j]:dp[1][i][j-1];
                //当前血量
                dp[1][i][j]+=from;
                dp[0][i][j]=min(dp[0][i][j],dp[1][i][j]);
            }
        }
        int res=dp[0].back().back();
        if(res>=0)return 1;
        return abs(res)+1;
    }
};
// 1  -3  3
// 0  -2  0
//-3  -3  -3
//dp[1][2] 这个位置不能仅仅通过前面的状态得到,而是需要知道后面要扣多少血,才能知道从哪里来;
//left: -1 -1 up: -3 3  here:0
//next -3
//需要改变状态表示,使得能推出状态转移方程,状态转移方程必须要是依赖已经算出来的值(填表方向相反)
//填表的方向可以从左向右或者从右向左
//dp[i][j]:   从这个格子开始到终点需要多少初始生命值
//状态转移方程: dp[i][j]=min(right,down)-dungeon[i][j];
//初始化:       dp[end][end]=dungeon[end][end]*-1;

class Solution {
public:
    // 1  -3  3      2  3  0
    // 0  -2  0      5  5  3
    //-3  -3  -3     9  6  3
    //dp[1][2] 这个位置不能仅仅通过前面的状态得到,而是需要知道后面要扣多少血,才能知道从哪里来;
    //left: -1 -1 up: -3 3  here:0
    //next -3
    //需要改变状态表示,使得能推出状态转移方程
    //dp[i][j]:   从这个格子开始到终点需要多少初始生命值
    //状态转移方程: dp[i][j]=min(right,down)+(dungeon[i][j]*-1);
    //初始化:       dp[end][end]=dungeon[end][end]*-1;
    //特殊: 从任何一个格子到终点的初始血量不能时负的,负的就是死了
    //返回值: 题目视作0就是死,实则格子里值代表-1才是死,只需要最后返回时做处理
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        dungeon.back().back()*=-1;
        if(dungeon.back().back()<=0)dungeon.back().back()=0;
        for(int i=dungeon.size()-1;i>=0;i--){
            for(int j=dungeon[i].size()-1;j>=0;j--){
                if(i==dungeon.size()-1&&j==dungeon[i].size()-1){
                    cout<<dungeon[i][j]<<' ';
                    continue;
                }
                int right=j+1<dungeon[i].size()?dungeon[i][j+1]:INT_MAX;
                int down=i+1<dungeon.size()?dungeon[i+1][j]:INT_MAX;
                dungeon[i][j]-=min(right,down);
                dungeon[i][j]*=-1;
                if(dungeon[i][j]<=0)dungeon[i][j]=0;
            }
        }
        if(dungeon.front().front()<=0)return 1;
        return dungeon.front().front()+1;
    }
};